﻿// 计算插入排序的时间  MEASURETIME.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://algospot.com/judge/problem/read/MEASURETIME

问题

插入排序是一种著名的排序算法，它通过维护一个已排序的子数组并将新元素插入该数组来进行排序。下面是插入排序算法的实现：

void insertionSort(vector<int>& A) {
for(int i = 0; i < A.size(); ++i) {
// Insert A[i] into A[0..i-1]
int j = i;
while(j > 0 && A[j-1] > A[j]) {
// Invariant a: All elements in A[j+1..i] are greater than A[j].
// Invariant b: The interval A[0..i] is sorted except for A[j].
swap(A[j-1], A[j]);
--j;
}
}
}

在插入排序中，当A[0..i-1]是已排序的数组时，A[i]会向左移动一位，直到找到合适的位置。例如，对于A={5,1,4,3,2}，插入排序的过程如下：

A	备注
5 1 4 3 2	初始状态
1 5 4 3 2	将1向左移动1位
1 4 5 3 2	将4向左移动1位
1 3 4 5 2	将3向左移动2位
1 2 3 4 5	将2向左移动3位

给定长度为N的序列A[]，编写一个程序来计算在排序过程中总共移动数字的次数。例如，上述数组中总共移动了1+1+2+3=7次。

输入
输入的第一行包含测试用例的数量C（1 <= C <= 50）。每个测试用例的第一行包含原始数组的长度N（1 <= N <= 50000）。接下来一行包含N个整数，表示A的元素Ai（0 <= Ai < 1,000,000）。

由于输入规模较大，请尽可能快地使用适当的输入函数。

输出
对于每个测试用例，每行输出在插入排序过程中移动数字的总次数。

示例输入
2
5
5 1 4 3 2
10
7 8 6 6 1 9 4 4 3 10

示例输出
7
25
*/
int main()
{
    std::cout << "Hello World!\n";
}

 